/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-07-27
 * Time: 20:08
 */
public class  Sort {

    public  static  void fun(int[] arr,int i,int j){
        int n=arr[i];
        arr[i]=arr[j];
        arr[j]=n;
    }

    // 选择排序
    public static void selectSort(int[] arr){
        if(arr.length==0){
            return;
        }
        int min;
        int i,j;
        for ( i = 0;i < arr.length; i++){
            min=i;
            for ( j = i+1; j < arr.length; j++) {
                if(arr[j]<arr[min])
                    min=j;
            }
            fun(arr,i,min);
        }
    }

    // 堆排序
    public static void heapSort(int[] arr){
        arrDown(arr);
        for(int i=arr.length ; i>0 ; i--){
            down(arr,0,i);
            fun(arr,0,i-1);
        }
    }

    public static void arrDown(int[] arr){
        int i=(arr.length-1-1)/2;
        while(i>=0){
            down(arr,i,arr.length);
            i--;
        }
    }
    public static void down(int[] arr,int root,int size){
        int s=root*2+1;
        if(s>=size){
            return;
        }
        while(s<size){
            if(s+1<size&&arr[s+1]>arr[s]){
                s++;
            }
            if(arr[s]>arr[root]){
                fun(arr,s,root);
            }
            else{
                return;
            }
            root=s;
            s=root*2+1;
        }
    }
}
